import java.util.Stack;

public class Sort {



    public static void insertSort(int[] arr){

        for(int i=1;i<arr.length;i++){
            int tmp=arr[i];
            int j=i-1;
            for (; j >=0; j--) {
                //tmp=arr[i];
                if(tmp < arr[j]){
                    arr[j+1]=arr[j];
                }else{
                    //arr[j+1]=tmp;
                    break;
                }
            }
            arr[j+1]=tmp;
            //稳定的排序
            //稳定可以由一个等号改变
            //一个本身就稳定的排序可以实现为，
        }
    }
    public static void shellSort(int []array){
        int gap=array.length;
        while(gap>1){
            gap/=2;
            shell(array,gap);
        }

    }
    //shell排序的时间复杂度，和增量有关系的
    //不稳定的排序
    public static void shell(int []array,int gap){
        for(int i=gap;i<array.length;i++){
            int tmp=array[i];
            int j=i-gap;
            for (; j >=0; j-=gap) {
                //tmp=arr[i];
                if(tmp < array[j]){
                    array[j+gap]=array[j];
                }else{
                    //arr[j+1]=tmp;
                    break;
                }
            }
            array[j+gap]=tmp;
            //所有的加1，变为加gap
            //
            //稳定的排序
            //稳定可以由一个等号改变
            //一个本身就稳定的排序可以实现为，
            //那个是n*n
            //

        }
    }

    public void selectSort(int array[]){
        for(int i=0;i<array.length;i++){
            int minIndex=i;
            for (int j = i+1; j <array.length ; j++) {
                if(array[minIndex]>array[j]){
                    minIndex=j;
                }
            }
            swap(array,minIndex,i);
        }
    }
    public static void swap(int []array,int i,int j){
        int tmp=0;
        tmp=array[i];
        array[i]=array[j];
        array[j]=tmp;
    }
    public static void selectSort2(int []array){
        int left=0;
        int right=array.length-1;
        while (left<right){
            int minIndex=left;
            int maxIndex=right;
            for (int i = left+1; i < right; i++) {
                if(array[i]>array[maxIndex]){
                    maxIndex=i;
                }
                if(array[i]<array[minIndex]){
                    minIndex=i;
                }
            }
            swap(array,minIndex,left);
            if(maxIndex==left){
                //最大值刚好在最小值的位置，
                //其实就是看你怎么写了，本质都是一样的
                maxIndex=minIndex;
            }
            swap(array,maxIndex,right);
            left++;
            right--;
        }
    }
    public static void heapSort(int []array){
        createBigHeap(array);
        int end=array.length-1;
        while (end>0){
            swap(array,0,end);
            siftDown(array,0,end);
            end--;
        }
    }
    public static void createBigHeap(int []array){
        for(int parent=(array.length-1-1)/2;parent>=0;parent--){
            siftDown(array,parent,array.length);

        }
    }
    private static void siftDown(int []array,int parent,int end){
        int child=2*parent+1;
        while(child<end){
            if((child+1)<end&&array[child]<array[child+1]){
                child++;
            }
            if(array[child]>array[parent]){
                swap(array,child,parent);
                parent=child;
                child=2*parent+1;
            }else{
                break;
            }
        }
    }
    public static void bubbleSort(int []array){
        for(int i=0;i<array.length-1;i++){
                boolean flg=false;
            for (int j = 0; j < array.length-1-i; j++) {
                if(array[j]>array[j+1]){
                    swap(array,j,j+1);
                    flg=true;
                }
            }
            if(!flg){
                break;
            }
        }
    }
    public static void quickSort(int []array){
        quick(array,0,array.length-1);
    }
    private static void insertSortRandom(int[] arr,int begin,int end){

        for(int i=begin;i<=end;i++){
            int tmp=arr[i];
            int j=i-1;
            for (; j >=begin; j--) {
                //tmp=arr[i];
                if(tmp < arr[j]){
                    arr[j+1]=arr[j];
                }else{
                    //arr[j+1]=tmp;
                    break;
                }
            }
            arr[j+1]=tmp;
            //稳定的排序
            //稳定可以由一个等号改变
            //一个本身就稳定的排序可以实现为，
        }
    }
    private static void quick(int []array,int start,int end){

        if(start>=end){
            return ;
        }
        if(end-start+1<=15){
            insertSortRandom(array,start,end);
            //
            return;
        }
        int pivot=partition(array,start,end);

        quick(array,start,pivot-1);
        quick(array,pivot+1,end);


    }
    //idea感觉有时候可以识别英文一样。
    //为什么不是left先董，而是right先董

    private static int partitionH(int[]array,int left,int right){//这个是找基准，划分区
        int key =left;
        while(left<right){
            while(left<right&&array[right]>=key){
                right--;
            }
            //为什么要先走right
            //反着走会怎么样？？？
            //
            array[left]=array[right];
            while(left<right&&array[left]<=key){
                left++;
            }
            array[right]=array[left];
        }
        array[left]=key;
        return left;
    }
    private static int partition(int[]array,int left,int right){//这个是找基准，划分区
        int key =left;
        int i=left;
        while(left<right){
            while(left<right&&array[right]>=key){
                right--;
            }
            //为什么要先走right
            //反着走会怎么样？？？
            //
            while(left<right&&array[left]<=key){
                left++;
            }

            swap(array,left,right);
        }
        swap(array,left,i);
        return left;
    }
    //希尔排序
    //冒泡：
    //插入：
    //两个都是遍历的，
    //
    //挖坑法：
    //暂时存放：挖坑
    //找到的基准好像一样：但是拿到的有不一样，不是很一样
    //Hoare
    //前后指针法---把前面大于基准的数字推着前进
    //prev在后面记录第一个大于基准的，cur到后面去找小的，必须在prev后
    //

    public static void quickSortNor(int[]array){
        Stack<Integer> stack=new Stack<>();
        int left=0;
        int right=array.length-1;
        int pivot=partition(array,left,right);
        if(pivot-1>left){
            stack.push(left);
            stack.push(pivot-1);
        }
        if(pivot+1<right){
            stack.push((pivot+1));
            stack.push(right);
        }
        while(!stack.isEmpty()){
            right=stack.pop();
            left=stack.pop();
            pivot=partition(array,left,right);
            if(pivot-1>left){
                stack.push(left);
                stack.push(pivot-1);
            }
            if(pivot+1<right){
                stack.push((pivot+1));
                stack.push(right);
            }
        }
        //这里说明，栈里面就没有了。
        //极端情况我不会使用快排

    }

    //归并排序：分解+合并
    //一路归并
    //二路归并
    //特别像二叉树
    //分解和并
    //只要分解完左边、分解完右边，就要合并
    public static void mergeSort(int []array){
        mergeSortFunc(array,0,array.length-1);
    }

    public static void mergeSortFunc(int []array,int left,int right){
        if(left>=right) return;
        int mid=(left+right)/2;
        mergeSortFunc(array,left,mid);
        mergeSortFunc(array,mid+1,right);
        merge(array,left,right,mid);
    }
    private static void merge(int[]array,int left,int right,int mid){
        //合并两个有序的数组---合并到一个新的数组
        int s1=left;
        int s2=mid+1;
        int k=0;
        int []tmpArr=new int[right-left+1];
        while(s1<=mid&&s2<=right){
            if(array[s1]<=array[s2]){
                tmpArr[k++]=array[s2++];
            }else {
                tmpArr[k++]=array[s1++];
            }
        }
        while(s1<=mid){
            tmpArr[k++]=array[s1++];
        }
        while(s2<=right){
            tmpArr[k++]=array[s2++];
        }
        for(int i=0;i<tmpArr.length;i++){
            array[i+left]=tmpArr[i];
        }
        //这个就是严格的二分
        //时间复杂度和空间复杂度，
    }
    public static void mergeSortNor(int[]array){
        int gap=1;
        while (gap<array.length){
            for (int i = 0; i < array.length; i+=2*gap) {
                int left=i;
                int mid=left+gap-1;
                int right=mid+gap;
                if(mid>=array.length){
                    mid=array.length-1;
                }
                if(right>=array.length){
                    right= array.length;
                }
                merge(array,left,right,mid);
            }
            //非递归实现：没有了拆分的过程
            //我们直接按照我们思维的拆分

            gap*=2;
        }
    }

     //明白它的思想，就是分分钟的事情
    //归并排序是外部排序常用的思路
    //读到内存，写回文件
    //每个小文件都有序
    //用两个文件指针，去分别对两个来读，
    //读出小的，放到内存
    //继续归并

    //不断地二路归并
    //输入输出流--这个东西懂了之后，就可以了
    //其他的非基于比较排序

    //基数排序
    //桶排序
    //
    public static void countSort(int []array){
        int minVal=array[0];
        int maxVal=array[0];
        for(int i=0;i<array.length;i++){
            if(array[i]>maxVal){
                maxVal=array[i];
            }
            if(array[i]<minVal){
                minVal=array[i];
            }
        }
        int []count=new int[maxVal-minVal+1];
        for (int i = 0; i < array.length; i++) {
            count[array[i]-minVal]++;
        }
        int index=0;
        for (int i = 0; i < count.length; i++) {
            while(count[i]>0){
                array[index]=i+minVal;
                index++;
                count[i]--;
            }
        }
        //计数排序
        //下面是红黑树
        //是一颗特殊的二叉搜索树
    }




    

}

